"""
跳跃游戏：

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:

假设你总是可以到达数组的最后一个位置。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

solution2是优化。
"""

class Solution:
    def __init__(self):
        self.memo = []

    def jump(self, nums: list) -> int:
        n = nums.__len__()
        self.memo = [n for i in range(n)]
        return self.dp(nums, 0)

    def dp(self, nums: list, p: int) -> int:
        n = nums.__len__()
        if p >= n - 1:  return 0
        if self.memo[p] != n:  return self.memo[p]

        steps = nums[p]
        for i in range(1, steps + 1):
            subProblem = self.dp(nums, p + i)
            self.memo[p] = min(self.memo[p], subProblem + 1)
        return self.memo[p]


class Solution2:
    def jump(self, nums: list) -> int:
        n = nums.__len__()
        end = 0
        farthest = 0
        jumps = 0
        for i in range(n - 1):
            farthest = max(nums[i] + i, farthest)
            if end == i:
                jumps += 1
                end = farthest
        return jumps


if __name__ == "__main__":
    lines=[1,2,3,4,5]
    n=lines[0]
    pi={}
    for p in lines[1:]:
        pi[int(p)]=0
    print(pi.get(3,'#'))
    print(list(map(int,'1 2\n'.split())))
    print(n,pi)
